Help Teju find the target efficiently!
Hi! I'm Teju 👋 I have a sorted array of numbers, and I need to find if a target value exists in it.
There are two ways to search: Linear Search (check one by one) and Binary Search (smart divide & conquer).
Input: A sorted array and a target number
Output: "Found at index X" or "Not found"
Goal: Compare how fast each algorithm finds (or doesn't find) the target!
Linear Search is simple: start from the beginning and check every element one by one until you find the target or reach the end.
Currently checking index 1 → Not target → Keep going →
Time Complexity: O(n) → May check all n elements
Best Case: Target at first position → O(1)
Worst Case: Target at end or not present → O(n)
Binary Search is super smart! Since the array is sorted, we can eliminate half of the remaining elements in each step!
Middle = 18, Target = 8 → Too high! Eliminate right half
Time Complexity: O(log n) → Halves search space each step!
Best Case: O(1) → Target at middle
Worst Case: O(log n) → Extremely fast even for millions of elements!
| Feature | Linear Search | Binary Search |
|---|---|---|
| Time Complexity | O(n) | O(log n) |
| Requires Sorted Array? | No | Yes |
| Best Case | O(1) (first element) | O(1) (middle) |
| Worst Case | O(n) | O(log n) |
| Space Complexity | O(1) | O(1) |
| Use When... | Small/unsorted data | Large sorted data |
Binary Search wins by a landslide when the array is sorted and large!
For 1 million elements: Linear might take 1 million steps → Binary takes only ~20 steps!